SGI Developer Toolbox 6.1

home *** CD-ROM | disk | FTP | other *** search

/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / csg / csg-paper < prev next >

Wrap

Text File | 1994-08-02 | 9.4 KB | 232 lines

toolbox/src/exampleCode/csg csg-paper Constructive Solid Geometry Stencil planes and solid geometry applications by Kurt Akeley References ---------- 1. "Near Real-Time CSG Rendering using Tree Normalization and Geometric Pruning." Jack Goldfeather, Steven Molnar, Greg Turk, and Henry Fuchs. 2. "Parallel Pixel Algorithms for Constructive Solid Geometry." Jim Clark and Paul Haeberli. Background ---------- CSG stands for constructive solid geometry. A CSG object is constructed of unions and intersections of proper primitive solids and their inverses. For example, a sphere with a circular hole 'drilled' in it can be constructed by intersecting the inverse of a cylinder with a sphere (thus subtraction is accomplished by intersection with an inverse). Our proposed algorithm requires that the CSG equation be first reduced to is normal form. This is the equivalent of reducing a boolean equation to disjunctive normal form, a sum of products. CSG operators union and intersection are equivalent to sum and product boolean operators. It is possible and desirable to eliminate unnecessary terms from this normalized equation [1]. Some Preliminaries ------------------ Crucial to the understanding of our CSG algorithm is the recognition that no new surfaces are created by the union and intersection of primitives. I.e., the surfaces of the final object are a subset of the surfaces of the primitives used to compose it. Also, let's start by considering only primitives that are proper convex solids. These solids are represented as sets of planer polygons. Proper polygonal surfaces separate space into two subspaces, one 'inside' and one 'outside'. Thus a proper polygon surface has no holes in it, and does not intersect itself. The polygonal surface is convex if any line that passes through the 'inside' volume intersects the surface exactly twice (once going in, once going out). The Algorithm ------------- Given the above, a very simple algorithm for computing a correct CSG projection (image) is possible: Along each line of sight (i.e. at each pixel) 1. Compute the color and depth of each surface that remains after all inversions and intersections are completed. 2. Choose the nearest color/depth pair. A high-level implementation of this algorithm is: 1. For every potentially visible primitive polygon, create a projection (color and depth) in a temporary buffer. 2. Test each pixel in this projection against the volumes with which it is being intersected. Force the z value of pixels that don't pass all the tests to infinity. 3. Merge all of these single-polygon images into an accumulation buffer, selecting the nearer color/z pair at each pixel. Just as back-facing polygons are never visible in a Z-buffer image, they also cannot be visible in a CSG image. Thus, in step 1 above, the potentially visible polygons are those that are front-facing. Unless, of course, the volume is inverted, in which case only back-facing polygons are potentially visible (because back-facing polygons form the surface that transistions from 'outside' to 'inside' along the view path). Regarding step 2, each pixel in the temporary buffer is either inside or outside every primitive with which it is intersected. Because all primitives are convex, they intersect each line of sight (pixel) either twice or not at all (note 1). The pixel in the temporary buffer is inside if only one intersection falls between the eyepoint and the pixel. It is outside if both or neither fall in this space, or if the pixel is not intersected. The test in step 2 above involves first determining whether the temporary buffer pixel is inside or outside each primitive (with which it is to be intersected), then determining whether it should have been inside or ourside. It should be outside if it is being intersected with the inverse of a primitive volume, inside otherwise. Pixels that fail the test are effectively eliminated from the temporary image by having their depth (z) values forced to infinity. These pixels will never be chosen during the merge into the accumulation buffer. The final step 2 note: (something about the expresion) Some optimizations to this algorithm are possible: 1. It is not necessary to render each polygon individually. It is necessary only to insure that the temporary buffer has at most one surface sample in each pixel. With convex primitives this can be accomplished by rendering each primitive once, eliminating either all front-facing polygons (if the volume is inverted) or all back-facing polygons (if it is not). 2. Only temporary buffer pixels that have non-infinite depths need be merged into the accumulation buffer. Although a pixel-by-pixel test would save no effort, it is possible to limit the merge to the screen-aligned buffer region that was modifed by the rendered primitive. These buffer boundries can be maintained with minimal effort during the render operation. 3. It is not necessary to compute or store color values during rendering to the temporary buffer. Rather, render only depth values, and merge these into the depth portion of the accumulation buffer. When the accumulation is completed, re-render each polygon in the scene, replacing color in the accumulation buffer only when the depth of the rendered pixel EXACTLY MATCHES the depth in the accumulation buffer. At the cost of re-rendering each polygon only once, both the color calculation and storage are saved throughout the execution. Pseudo-code Implementation -------------------------- initialize the accumulation buffer (background color, near-infinite z) initialize the tmp buffer (infinite z, zero count) for (each primitive) { initialize the bound-measuring hardware if (primitive is inverted) render the back-facing primitive depth values into the tmp buffer else render the front-facing primitive depth values into the tmp buffer transfer measured primitive bounds to the bound-limit hardware (allow NO changes to the tmp buffer outside the bounds) for (each intersecting primitive) { render just the depth values for (each rendered pixel) { increment the tmp buffer pixel counter if rendered depth is between the eyepoint (zero) and the depth value in the temporary buffer do NOT replace the depth value in the tmp buffer } for (each pixel in the bounded region) { if (intersecting primitive is inverted) { if (count is 1) force tmp buffer z value to infinity } else if (not inverted) { if (count is 0 or 2) force tmp buffer z value to infinity } } } for (each pixel in the bounded region) { if (depth is less than corresponding depth in accumulation) replace accumulation buffer depth with tmp depth set tmp buffer depth to infinity set tmp buffer count to zero } disable bound-limit hardware (allow changes throughout the tmp buffer area) } for (each primitive) { render with color and depth for (each rendered pixel) { if (depth matches accumulation buffer depth) replace accumulation buffer color with new color } } Non-convex Primitives --------------------- The surface of a convex volume is intersected twice by a line that passes through the 'inside'. We can extend the notion of convexity to include more complex volumes by defining a convexity number. This number is the maximum number of intersections that a line passing through the 'inside' can have with the surface, divided by two. Thus simple convex volumes have a convexity of one. A taurus (do-nut) has a convexity of two. We speak in general of k-convex volumes, where k is the convexity number. Our algorithm is easily extended to k-convex primitives. Two issues need to be addressed: 1. A k-convex primitive must be rendered into the temporary buffer 2k times to insure that each potential surface is given the opportunity to be visible. 2. The inside/outside test must be extended to work with more complex volumes. The first issue is handled by providing a mechanism that, at each pixel, renders the n'th depth value received. By doing k renders (front-face and back-face) of a primitive into the temporary buffer, with n set to 1 through k, it is possible to insure that each surface is represented (note 2). Because we require that our k-convex volumes also have nonself-intersecting surfaces, we know that a line that passes through the 'inside' of the volume alternates inside/outside each time it intersects the surface. Thus, rather than testing for a count of 1 to indicate 'inside', we can simply check for an odd count. Incorporating these two modifications to the algorithm is left as an exercise for the reader. Notes ----- 1. Proper point sampling of polygons during rendering is absolutely required by this CSG algorithm. Adjacent polygons must neither share any pixels, nor leave any pixels unfilled (i.e. they must abut exactly). If this is done correctly, even pixels whose sample point is exactly on a silhouette edge of the polygonal volume will correctly register two hits (even though the ray does not pass through the 'inside' volume). 2. Not all pixels will receive k distinct values. It is very possible that none will. A possible optimization involves determining the maximum number of times that any pixel is intersected by the primitive, and doing this number of passes (regardless of the convexity of the primitive).